#include<stdio.h>

/**法一：相减法 也叫更相减损法
 * 思路：
 * 1、如果a > b a = a - b;
 * 2、如果b > a b = b - a;
 * 3、假如a = b,则 a或 b是最大公约数；
 * 4、如果a != b;则继续从一开始执行；
 * 5、也就是说循环的判断条件为a != b,直到a = b时，循环结束。
 */ 
int gcd_way01(int numa, int numb) {
    while(numa != numb)
    {
        if(numa > numb)
            numa = numa - numb;
        if(numa < numb)
            numb = numb - numa;
    }
    return numa;
}


/**法二：--好理解
 * 思路：
 * 1.选出a，b中最小的一个数字放到c中
 * 2.分别用a，b对c求余数，即看是否能被c整除
 * 3.直到a，b同时都能被c整除
 * 4.如不能整除，c– (c的值减一) 继续从2开始执行
 * 5.也就是说该循环的判断条件为 a，b能否同时被c整除，只要有一个数不能被c整除，循环继续执行
 */ 
int gcd_way02(int a, int b) {
    int c = (a>b)?b:a;
    while((a%c != 0) || (b%c != 0))
    {
        c--;
    }
    return c;
}


/**法二：辗转相除法
 * 思路：
 * 1.将两整数求余 a%b = c
 * 2.如果c = 0;则b为最大公约数
 * 3.如果c != 0,则 a = b；b = c；继续从1开始执行
 * 4.也就是说该循环的是否继续的判断条件就是c是否为0
 */ 
int gcd_way03(int a, int b) {
    int c = c = a%b;
    while(c)
    {
        a = b;
        b = c;
        c = a%b;
    }
    return b;
    // 可以简化为  return b == 0? a: gcd_way03(b, a % b);
}



int main(int argc, char **argv) {
    int numa = 13, numb=6;
    int numa = 12, numb=6;
    printf("%d 与 %d的最大公约数为：%d\n", numa, numb,gcd_way01(numa,numb));
    printf("%d 与 %d的最大公约数为：%d\n", numa, numb,gcd_way02(numa,numb));
    printf("%d 与 %d的最大公约数为：%d\n", numa, numb,gcd_way03(numa,numb));
}